package advance.day06;
import java.util.LinkedList;

/**
 * 描述：
 *      输入一个字符串类型的表达式，假设输入的字符串是合法的，计算表达式的结果\
 *      将每一个括号里的内容看做一个子过程，递归求解
 * @author hl
 * @version 1.0
 * @date 2020/11/12 9:22
 */
public class ExpressionCompute {
    public static int getValue(String str){
        return value(str.toCharArray(), 0)[0];
    }

    private static int[] value(char[] str, int i) {
        LinkedList<String> queue = new LinkedList<>();
        int pre = 0;
        int[] subProcessRes = null;
        while(i < str.length && str[i] != ')'){
            if (str[i] >= '0' && str[i] <= '9') {
                pre = pre * 10 + str[i++] - '0';
            }else if (str[i] != '(') {
                addNum(queue, pre);
                queue.addLast(String.valueOf(str[i++]));
                pre = 0;
            }else {
                subProcessRes = value(str, i + 1);
                pre = subProcessRes[0];
                i = subProcessRes[1] + 1;
            }
        }
        addNum(queue, pre);
        return new int[]{getNum(queue),i};
    }

    private static int getNum(LinkedList<String> queue) {
        int res = 0;
        boolean add = true;
        String cur;
        while(!queue.isEmpty()){
            cur = queue.pollFirst();
            if (cur.equals("+")) {
                add = true;
            }else if (cur.equals("-")) {
                add = false;
            }else{
                int num = Integer.valueOf(cur);
                res += add ? num : (-num);
            }
        }
        return res;
    }

    private static void addNum(LinkedList<String> queue, int num) {
        if (!queue.isEmpty()) {
            int cur = 0;
            String top = queue.pollLast();
            //先不管+-，只将*/进行运算
            if (top.equals("+") || top.equals("-")) {
                queue.addLast(top);
            }else {
                cur = Integer.valueOf(queue.pollLast());
                num = top.equals("*") ? (cur * num) : (cur / num);
            }
        }
        queue.addLast(String.valueOf(num));
    }
    public static void main(String[] args) {
        String exp = "48*((70-65)-43)+8*1";
        System.out.println(getValue(exp));

        exp = "4*(6+78)+53-9/2+45*8";
        System.out.println(getValue(exp));

        exp = "10-5*3";
        System.out.println(getValue(exp));

        exp = "-3*4";
        System.out.println(getValue(exp));

        exp = "3+1*4";
        System.out.println(getValue(exp));
    }
}
